
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    map<Node*,Node*> *list = new map<Node*,Node*>();

    Node* copyRandomList(Node* head) {
        if(head==NULL) return NULL;
        return deepCopy(head);
    }

    Node* deepCopy(Node* target){
        if(target==NULL) return NULL;
        if(list->empty()==false){
            map<Node*,Node*>::iterator iter = list->find(target);
            if(iter!=list->end())
                //说明已经存在一个深拷贝的对象，直接返回
                return (*iter).second;
        }
        //否则开始深拷贝
        Node* copyNode = new Node(target->val);
        list->insert(pair<Node*,Node*>(target,copyNode)); //保存已经深拷贝的节点
        copyNode->next = deepCopy(target->next);
        copyNode->random = deepCopy(target->random);
        return copyNode;
    }
};
int main(){
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    n1->next = n2;
    n1->random = n2;
    n2->random = n2;
    Solution* solution = new Solution();
    Node* copyNode = solution->copyRandomList(n1);
    return 0;
}